import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"

/**
 * 归并排序是一个分而治之算法，将原始数组切分成比较小的数组，
 * 直到每个小数组只有一个位置，接着将小数组归并成比较大的数组，
 * 直到最后只有一个排序完毕的大数组。
**/
export class MergeSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(array: T[] = this.array): Array<T> {
        if (array.length > 1) {
            const { length } = array;
            // 获取中间值
            const middle = Math.floor(length / 2);
            // 递归填充左右数组
            const left = this.sort(array.slice(0, middle));
            const right = this.sort(array.slice(middle, length));
            // 合并左右数组
            array = this.merge(left, right);
        }
        return array;
    }

    private merge(left: Array<T>, right: Array<T>): Array<T> {
        let i: number = 0;
        let j: number = 0;
        const result: Array<T> = new Array<T>()
        while (i < left.length && j < right.length) {
            // 如果left[i] < right[j]将left[i]加进result中，随后i自增，否则把right[j]加进result中，随后j自增
            result.push(this.compare.compare(left[i], right[j]) === CompareEnum.LESS ? left[i++] : right[j++])
        }
        //将left或right数组的剩余项添加进result中
        return result.concat(i < left.length? left.slice(i) : right.slice(j))
    }
}

const InsertionSortTest = (): void => {
    const array = [123, 424, 637, 154, 541]
    const mergeSort: Sort<Number> = new MergeSort<Number>(array)
    console.log(mergeSort.sort());
}
InsertionSortTest()